#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void MergeSortNonR(int* a,int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail\n");
        return;
    }
    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            
            if (end1 >= n || begin2 >= n)
            {
                break;
            }
            if (end2 >= n)
            {
                end2 = n - 1;
            }

            int j = i;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] <= a[begin2])
                {
                    tmp[j++] = a[begin1++];
                }
                else
                {
                    tmp[j++] = a[begin2++];
                }
            }

            while (begin1 <= end1)
            {

                tmp[j++] = a[begin1++];

            }

            while (begin2 <= end2)
            {
                tmp[j++] = a[begin2++];
            }
            memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
        }
        gap *= 2;

    }


    free(tmp);

}

void CountSort(int* a, int n)
{
    int max = a[0], min = a[0];
    for (int i = 0; i < n; i++)
    {
        if (max < a[i])
        {
            max = a[i];
        }
        if (min > a[i])
        {
            min = a[i];
        }
    }

    int range = max - min + 1;
    int* countA = (int*)calloc(range,sizeof(int));
    for (int i = 0; i < n; i++)
    {
        countA[a[i] - min]++;
    }

    int j = 0;
    for (int i = 0; i < range; i++)
    {
        while (countA[i]--)
            a[j++] = i + min;
    }

    free(countA);
}


int main()
{
	int arr[] = { 9,12,5,8,21,7,8,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
    CountSort(arr, sz);
	//MergeSortNonR(arr, sz);
	return 0;
}